import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        //用数组模拟队列
        List<Pair<TreeNode, Integer>> q = new ArrayList();
        q.add(new Pair<TreeNode, Integer>(root, 1));
        int ret = 0;//记录最终结果

        while (!q.isEmpty()) {
            //先更新一下这层的宽度
            Pair<TreeNode, Integer> t1 = q.get(0);
            Pair<TreeNode, Integer> t2 = q.get(q.size() - 1);
            ret = Math.max(ret, t2.getValue() - t1.getValue() + 1);

            //让这一层进队列
            List<Pair<TreeNode, Integer>> tmp = new ArrayList();
            for (Pair<TreeNode, Integer> t : q) {
                TreeNode node = t.getKey();
                int index = t.getValue();

                if (node.left != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.left, 2 * index));
                }
                if (node.right != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.right, 2 * index + 1));
                }
            }
            q = tmp;
        }

        return ret;
    }
}